100. BABTWR - Tower of Babylon

Apart from the Hanging Gardens the Babylonians (around 3000-539 b.c.) built the Tower of Babylon as well. The tower was meant to reach the sky, but the project failed because of a confusion of language imposed from much higher above.

For the 2638th anniversary a model of the tower will be rebuilt. n different types of blocks are available. Each one of them may be duplicated as many times as you like. Each type has a height y, a width x and a depth z. The blocks are to be stacked one upon eachother so that the resulting tower is as high as possible. Of course the blocks can be rotated as desired before stacking. However for reasons of stability a block can only be stacked upon another if both of its baselines are shorter.

Input. The number of types of blocks n is located in the first line of each test case. On the subsequent n lines the height y_i, the width x_i and the depth z_i of each type of blocks are given. There are never more than 30 different types available.

There are many test cases, which come one by one. Input terminates with n = 0.

Output. For each test case your program should output one line with the height of the highest possible tower.

Sample input	Sample output
5 31 41 59 26 53 58 97 93 23 84 62 64 33 83 27 1 1 1 1	342 1

РЕШЕНИЕ

динамическое программирование

Анализ алгоритма

У нас имеются n различных типов блоков, самих блоков каждого типа бесконечное множество. Пирамида может содержать блоки одного типа. Ставить одинаковые блоки друг на друга нельзя: обе стороны верхнего блока должны быть строго меньше соответствующих сторон нижнего блока. Каждый блок (x, y, z) можно вращать, поэтому вместе с ним будем рассматривать также блоки (y, z, x) и (z, x, y). Введем отношение f(a, b) частичного порядка, означающее что на блок a можно сверху поставить блок b. Отсортируем блоки согласно этого отношения.

Пусть dp[i] содержит максимальную высоту башни, которую можно сложить из первых i блоков при условии, что i-ый блок лежит на верху башни. Изначально положим dp[i] равным высоте i-го блока. Далее вычислим

dp[i] =,

где максимум берется по всем таким j, что на блок j можно поставить блок i. Ответом будет максимальное значение среди dp[i].

Реализация алгоритма

#include <cstdio>

#include <vector>

#include <algorithm>

using namespace std;

struct box

{

int x, y, z;

box (int x, int y, int z) : x(x), y(y), z(z) {}

};

vector<box> brick;

vector<int> dp;

int i, j, n, N, a, b, c, res;

int f(box a, box b)

{

return (((a.x < b.x) && (a.y < b.y)) ||

((a.x < b.y) && (a.y < b.x)));

}

int main(void)

{

while(scanf("%d",&n), n)

{

N = 3*n;

dp.clear(); dp.resize(N);

brick.clear();

for(i = 0; i < n; i++)

{

scanf("%d %d %d",&a,&b,&c);

brick.push_back(box(a,b,c));

brick.push_back(box(b,c,a));

brick.push_back(box(c,a,b));

}

// partial order, sort does not work!

for(i = 0; i < N; i++)

for(j = i + 1; j < N; j++)

if (f(brick[j],brick[i])) swap(brick[i],brick[j]);

for(res = -1, i = 0; i < N; i++)

{

dp[i] = brick[i].z;

for(j = 0; j < i; j++)

if(f(brick[j],brick[i]))

dp[i] = max(dp[i],dp[j] + brick[i].z);

res = max(res,dp[i]);

}

printf("%d\n",res);

}

return 0;

}